#include <stdio.h>
#include <stdlib.h>

/* 二叉查找树 */

typedef struct tree
{
    int val;
    struct tree *left;
    struct tree *right;
} Tree, *TreePtr;

/* 构建二叉树 */
void insert(TreePtr *node, int val);

/* 二叉树中序遍历 */
void inOrder(Tree *p);

void main()
{
    int array[] = {33, 16, 50, 13, 18, 34, 58};
    int len = 7;

    TreePtr root = NULL;

    for (int i = 0; i < len; i++)
    {
        insert(&root, array[i]);
    }

    inOrder((Tree*)root);
}

/* 构建二叉树 */
void insert(TreePtr *node, int val)
{
    TreePtr p;

    if (*node == NULL)
    {
        *node = (TreePtr)malloc(sizeof(Tree));
        (*node)->val = val;
        (*node)->left = NULL;
        (*node)->right = NULL;
        return;
    }
    else
    {
        p = *node;
        while (p != NULL)
        {
            if (val >= p->val)
            {
                if (!p->right)
                {
                    p->right = (TreePtr)malloc(sizeof(Tree));
                    p->right->val = val;
                    p->right->left = NULL;
                    p->right->right = NULL;
                    return;
                }
                p = p->right;
            }
            else
            {
                if (!p->left)
                {
                    p->left = (TreePtr)malloc(sizeof(Tree));
                    p->left->val = val;
                    p->left->left = NULL;
                    p->left->right = NULL;
                    return;
                }
                p = p->left;
            }
        }
    }
}

/* 二叉树中序遍历 */
void inOrder(Tree *p)
{
    if (p != NULL)
    {
        inOrder(p->left);
        printf("%d\n", p->val);
        inOrder(p->right);
    }
}